package com.wx.learn.sort;

/**
 * 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
 * <li>从数列中挑出一个元素，称为 “基准”（pivot）；</li>
 * <li>重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；</li>
 * <li>递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。</li>
 * @author wangxin
 */
public class QuickSort {

    public static void quickSort(int[] s, int l, int r) {
        if (l < r) {
            int pivot = s[l];
            int low = l, high = r;
            while (low < high) {
                //从大到小，找到比当前基数小的元素位置
                while (low < high && pivot <= s[high]) {
                    high--;
                }
                //将小元素放置在low处，及基数左边
                if (low < high) s[low++] = s[high];

                //从小到大找到比当前基数大的元素位置
                while (low < high && pivot >= s[low]) {
                    low++;
                }
                //将大元素放在high处，及基数右边
                if (low < high) s[high--] = s[low];
            }
            s[low] = pivot;

            //此处low处元素已找到正确位置，不需要再参与排序
            //递归排序
            quickSort(s, l, low - 1);
            quickSort(s, low + 1, r);
        }
    }

    public static void main(String[] args) {
        int[] s = {4, 3, 2, 5, 1, 6, 7, 8, 9, 10};
        quickSort(s, 0, s.length - 1);
        for (int i = 0; i < s.length; i++) {
            System.out.println(s[i]);
        }
    }

}
